1. Field of the Invention
The present invention relates to a multi-hop wireless communication system and its nodes.
2. Description of the Related Art
A multi-hop wireless communication system enables wireless nodes that are not within direct radio range of each other to communicate by relay through intermediate wireless nodes. Various routing protocols are used to ensure that communications are relayed over appropriate routes. For example, in ZigBee Specification Revision 17 (ZigBee Document 053474r17), the ZigBee Alliance has standardized a many-to-one routing protocol that enables a so-called sink node to collect data efficiently from a plurality of other nodes. Applications in environmental sensing and telemetering are envisioned.
The ZigBee protocol and other similar protocols are based on link costs. A link cost is quantity that indicates the quality or reliability of a direct (one-hop) wireless link between two neighboring nodes. In one implementation of the ZigBee system, each wireless node transmits link status packets (called frames) at, for example, 15-second intervals to its neighboring nodes. The nodes at the two ends of a direct wireless link can determine the cost of the link by measuring the percentage of these transmitted packets that are successfully received, by measuring the signal strength and/or data quality of the received packets, or by using a link quality indicator (LQI) provided in the packets.
The ZigBee many-to-one routing system is illustrated in FIGS. 17A to 17C for a network in which a sink node S (marked ‘a’) collects sensing data from nodes Nb to Nj (marked ‘b’ to ‘j’). The sink node S may submit the collected data to another device (not shown) via another network, indicated by the horizontal line at the top of these drawings. A typical one of nodes Nb to Nj will be referred to simply as a node N.
In FIG. 17A, the sink node S has broadcast a route request (RREQ) command. In ad-hoc on-demand distance vector routing schemes this command is commonly used to find a route between specific nodes, but in many-to-one routing this command is transmitted with a broadcast address and is used to enable an arbitrary node N to find a route to the sink node S.
A node N that receives the RREQ command relays it to other neighboring nodes. The relay processing includes adding the link cost of the link by which the command was received to a path cost value in the command, so that the path cost indicates the cumulative cost of the path taken by the packet from node S to node N. By selecting the neighboring node from which the RREQ command is received with the lowest path cost, for example, a node N can determine the best node to which to relay packets destined for node S. As the RREQ command propagates through the network, upstream paths from each node N to the sink node S are established.
In FIG. 17B, node Nh has transmitted a route record (RREC) command to establish a downstream path to itself from the sink node S. Each node that receives the RREC command adds its own address to a list of addresses in the command and relays the command toward node S. When the RREC command reaches node S, node S stores the address list, which indicates the path taken by the command (Nh to Nd to Nc to Nb to S).
In FIG. 17C, the sink node S has received RREC commands from all nodes N in the network and has acquired address lists describing a path to itself from each node N. When the sink node S transmits a packet to a specific node, it reads the address list from that node in reverse and places the reversed address list in the header of the packet. A node that receives the packet deletes its own address and relays the packet to the next node in the address list.
As network size increases, however, the concentration of all network traffic onto a single sink node leads to problems. One proposed solution is a network with a plurality of sink nodes that share the traffic load. An example of this type of multiple-sink network can be found in Oyman et al., ‘Multiple Sink Network Design Problem in Large Scale Wireless Sensor Networks’, Proc. International Conference on Communications (2004).
The existence of a plurality of sink nodes in a network enables an arbitrary node to discover an upstream path to each sink node, select the path with the lowest cost, and associate with or ‘connect to’ the sink node at the end of that path. This process tends to balance the loads on the sink nodes by balancing the numbers of nodes to which they are connected. However, to ensure that a RREQ command will be relayed throughout the network, the time-to-live (TTL) field in this command, which specifies the maximum number of times the command can be relayed, must be set to a large initial value such as 255. As a result, the amount of network traffic used for relaying RREQ commands increases, and the data communication throughput of the network suffers correspondingly.
Another advantage cited for having multiple sink nodes in a network is that if a sink node fails, its connections can be shifted to other sink nodes. With conventional many-to-one routing, however, in which once a node has selected a low cost path it continues to select that path until it receives a RREQ command with a lower path cost, a node that has a multi-hop connection to the failed sink node has no ready way to detect that the sink node to which it is connected has failed.
A further problem is that to switch its connection from a first sink node that has failed to a second sink node that is working, a node must inform the second sink node of the switchover. This can be done by transmitting a RREC command to the second sink node, but if all the nodes that switch their connections from the first sink node to the second sink node send RREC commands at the same time, the resulting concentration of traffic on the second sink node leads to collisions and other problems, and the second sink node may be unable to obtain accurate information about the nodes to which it is now connected.
There is accordingly a need for a multi-hop communication system with multiple sink nodes that generates less routing traffic and can respond more efficiently to sink node failures.